/*
 * @lc app=leetcode.cn id=968 lang=javascript
 *
 * [968] 监控二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

/**
 * a: 根结点放置摄像头
 * b: 不考虑根结点是否有摄像头
 * c: 不考虑根结点是否被监控，两棵子树被监控
 */

var minCameraCover = function(root) {
  const dfs = (root)=>{
    if(!root) return [Math.floor(Number.MAX_SAFE_INTEGER / 2), 0, 0];
    const [la,lb,lc] = dfs(root.left);
    const [ra,rb,rc] = dfs(root.right);
    let a = lc + rc + 1; // 左右子树被监控 + 根结点一个摄像头
    // Math.min(la + rb, ra + lb) 左子节点必有，右子节点必有，取最小
    let b = Math.min(a, Math.min(la + rb, ra + lb));
    let c = Math.min(a, (lb + rb));
    return [a, b, c];
  }
  return dfs(root)[1];
};
// @lc code=end

